Intro

We said an intelligent agent takes perceptual history and converts to action

Percepts -> actions

Planning helps in action selection.

Propositional Logic

Description	P Logic
Robot has to paint the ceiling	Painted(Ceiling)
Robot has to paint the ladder	Painted(Ladder)
Conjunction	Painted(Ceiling) & Painted(Ladder)

States

Exercise

Operator

• By convention, precondition has all literals positive, postcondition may have negative literals
• precondtion results are true in world before operator applied
• postcondition results will become true in world after operator applied
• operator can be applied only if precondition is true

Exercise

descend-ladder precondition: Robot should be already on Ladder, and Ladder should be dry postcondition: Robot is on floor

paint-ceiling pre: Robot should be on Ladder, Ladder is dry, and Ceiling is also dry post: ceiling painted and not dry anymore

paint-ladder pre: Robot should be on Floor and ladder dry post: ladder painted and not dry anymore

Correct answer:

Make sure to correct to have only positive literals in pre conditions

Planning and State Spaces

Note how states where the operator is applied satisfies both pre and post condition (and that is why that operator was selected in first place). Also note statse have negative literals, while operator preconditions do not.

MEA problem

Step 1

Current State: on which operators should be applied next

Current State
On(Robot, Floor) & Dry(Ladder) & Dry(Ceiling)

Available Operators

Operator	Pre condition	Post Condition
climb-ladder	On(Robot, Floor) & Dry(Ladder)	On(Robot, Ladder)
descend-ladder	On(Robot, Ladder) & Dry(Ladder)	On(Robot, Floor)
paint-ceiling	On(Robot, Ladder)	Painted(Ceiling) & !Dry(Ceiling)
paint-ladder	On(Robot, Floor)	Painted(Ladder) & !Dry(Ladder)

Applicable Operators: If not applicable, can be down right rejected anyway.

Operator	Pre condition	Post Condition	Applicability	Why?
climb-ladder	On(Robot, Floor) & Dry(Ladder)	On(Robot, Ladder)	yes	pre condition satisfied
descend-ladder	On(Robot, Ladder) & Dry(Ladder)	On(Robot, Floor)	no	pre condition not satisfied
paint-ceiling	On(Robot, Ladder)	Painted(Ceiling) & !Dry(Ceiling)	no	pre condition not satisfied
paint-ladder	On(Robot, Floor)	Painted(Ladder) & !Dry(Ladder)	yes	pre condition satisfied

Delta: For those applicable, which ever has least delta should be chosen

Operator	Current State	Post Condition	Next State	Delta
climb-ladder	On(Robot, Floor) & Dry(Ladder) & Dry(Ceiling)	On(Robot, Ladder)	On(Robot, Ladder) & Dry(Ladder) & Dry(Ceiling)	2
paint-ladder	On(Robot, Floor) & Dry(Ladder) & Dry(Ceiling)	Painted(Ladder) & !Dry(Ladder)	On(Robot, Floor) & !Dry(Ladder) & Dry(Ceiling) & Painted(Ladder)	1

So paint-ladder is best choice as per MEA at this step

Step 2

Current State:

Current State
On(Robot, Floor) & !Dry(Ladder) & Dry(Ceiling) & Painted(Ladder)

Available Operators

Operator	Pre condition	Post Condition
climb-ladder	On(Robot, Floor) & Dry(Ladder)	On(Robot, Ladder)
descend-ladder	On(Robot, Ladder) & Dry(Ladder)	On(Robot, Floor)
paint-ceiling	On(Robot, Ladder)	Painted(Ceiling) & !Dry(Ceiling)
paint-ladder	On(Robot, Floor)	Painted(Ladder) & !Dry(Ladder)

Applicable Operators: Based on satisfying pre condition..

Operator	Pre condition	Post Condition	Applicability
climb-ladder	On(Robot, Floor) & Dry(Ladder)	On(Robot, Ladder)	No
descend-ladder	On(Robot, Ladder) & Dry(Ladder)	On(Robot, Floor)	No
paint-ceiling	On(Robot, Ladder)	Painted(Ceiling) & !Dry(Ceiling)	No
paint-ladder	On(Robot, Floor)	Painted(Ladder) & !Dry(Ladder)	yes

MEA according to me is stuck in a conflict of painting again and again.

Exercise: Partial Order Planning

Sample

Current State

Current State
On(Robot, Floor) & Dry(Ladder) & Dry(Ceiling)

Applicable Operators

Operator	Pre condition	Post Condition	Applicability
climb-ladder	On(Robot, Floor) & Dry(Ladder)	On(Robot, Ladder)	yes
descend-ladder	On(Robot, Ladder) & Dry(Ladder)	On(Robot, Floor)	no
paint-ceiling	On(Robot, Ladder)	Painted(Ceiling) & !Dry(Ceiling)	no
paint-ladder	On(Robot, Floor)	Painted(Ladder) & !Dry(Ladder)	yes

Delta for applicable operators

Operator	Current State	Post Condition	Next State	Delta
climb-ladder	On(Robot, Floor) & Dry(Ladder) & Dry(Ceiling)	On(Robot, Ladder)	On(Robot, Ladder) & Dry(Ladder) & Dry(Ceiling)	1
paint-ladder	On(Robot, Floor) & Dry(Ladder) & Dry(Ceiling)	Painted(Ladder) & !Dry(Ladder)	On(Robot, Floor) & !Dry(Ladder) & Dry(Ceiling) & Painted(Ladder)	0

Not unlike earlier, this time, delta has reduced. Thus again paint-ladder is best choice for reduced goal of Painted(Ladder)

Exercise

Step 1

Current State

Current State
On(Robot, Floor) & Dry(Ladder) & Dry(Ceiling)

Applicable Operators

Operator	Pre condition	Post Condition	Applicability
climb-ladder	On(Robot, Floor) & Dry(Ladder)	On(Robot, Ladder)	yes
descend-ladder	On(Robot, Ladder) & Dry(Ladder)	On(Robot, Floor)	no
paint-ceiling	On(Robot, Ladder)	Painted(Ceiling) & !Dry(Ceiling)	no
paint-ladder	On(Robot, Floor)	Painted(Ladder) & !Dry(Ladder)	yes

Delta for applicable operators

Operator	Current State	Post Condition	Next State	Delta
climb-ladder	On(Robot, Floor) & Dry(Ladder) & Dry(Ceiling)	On(Robot, Ladder)	On(Robot, Ladder) & Dry(Ladder) & Dry(Ceiling)	1
paint-ladder	On(Robot, Floor) & Dry(Ladder) & Dry(Ceiling)	Painted(Ladder) & !Dry(Ladder)	On(Robot, Floor) & !Dry(Ladder) & Dry(Ceiling) & Painted(Ladder)	1

But paint-ladder was already used in another sub goal. So only left out candidate is climb-ladder

Step 2

Current State

Current State
On(Robot, Ladder) & Dry(Ladder) & Dry(Ceiling)

Applicable Operators

Operator	Pre condition	Post Condition	Applicability
climb-ladder	On(Robot, Floor) & Dry(Ladder)	On(Robot, Ladder)	x
descend-ladder	On(Robot, Ladder) & Dry(Ladder)	On(Robot, Floor)	$$\checkmark$$
paint-ceiling	On(Robot, Ladder)	Painted(Ceiling) & !Dry(Ceiling)	$$\checkmark$$
paint-ladder	On(Robot, Floor)	Painted(Ladder) & !Dry(Ladder)	x

Delta for applicable operators

Operator	Current State	Post Condition	Next State	Delta
descend-ladder	On(Robot, Ladder) & Dry(Ladder) & Dry(Ceiling)	On(Robot, Floor)	On(Robot, Floor) & Dry(Ladder) & Dry(Ceiling)	1
paint-ceiling	On(Robot, Ladder) & Dry(Ladder) & Dry(Ceiling)	Painted(Ceiling) & !Dry(Ceiling)	On(Robot, Ladder) & Dry(Ladder) & Painted(Ceiling) & !Dry(Ceiling)	0

So here, paint-ceiling is next logical operator. Applying that,

Detecting Conflicts

List out pre conditions of operators

Abbreviation	State
S1	On(Robot, Floor) & Dry(Ladder) & Dry(Ceiling)
S2	On(Robot, Floor) & !Dry(Ladder) & Dry(Ceiling) & Painted(Ladder
S3	On(Robot, Ladder) & Dry(Ladder) & Dry(Ceiling)
S4	On(Robot, Ladder) & Dry(Ladder) & Painted(Ceiling) & !Dry(Ceiling)

Finding conflicts: shown by tick indicator.

For an operator in a plan/goal, find conflicts in other plan/goal. For eg, for paint-ladder, find in goal:Painting(ceiling) plan.

Operator	Pre condition	S1	S2	S3	S4
paint-ladder	On(Robot, Floor)	x	NA	x	x
climb-ladder	On(Robot, Floor) & Dry(Ladder)	x	$$\checkmark$$	NA	NA
paint-ceiling	On(Robot, Ladder)	x	x	NA	NA

climb-ladder has Dry(Ladder) and S2 has !Dry(Ladder) which is a conflict. So prefer the goal first where climb-ladder was involved and then go for other goal.

Open Preconditions

Note S3 of Painted(Ceiling) the robot is on ladder, but S1 of Painted(Ladder) needs to have robot on floor. So there is a gap. Simply find from the remaining operators, which has the pre condition match with S3 of Painting(Ceiling) and post condition match with S1 of Painting(Ladder). Naturally its the descend-ladder

Postulates

• Knowledge is not just about world. Its also control-knowledge to select between operators
• Goals provide control knowledge
• Partial Order planning as interaction between several smaller agent with simpler goals independently
• Society of Mind is an example

Quiz: Partial Order Planning (POP) I

Quiz: POP II

Note, in order to move an X or Y, both should not have anything on top of them. This can be indicated by clear(x) for example.

Quiz: POP III

When they ask plans, write the operators list

Quiz: POP IV

Find Conflicts

Goal: On(A,B)

Goal: On(B,C)

Goal: On(C,D)

$$ \newcommand{\ch}{\checkmark} $$

Since S1, S2, S3 are common for all plans, we could ignore them for a moment.

Abbreviation	State	Goal:On(A,B)	Goal:On(B,C)	Goal:On(C,D)
S4	On(D,Table) & On(B,Table) & On(A,B) & On(C,Table)	$\ch$	x	x
S5	On(D,Table) & On(B,Table) & On(A, Table) & On(C,Table)	x	$\ch$	$\ch$
S6	On(D,Table) & On(B,C) & On(A,Table) & On(C,Table)	x	$\ch$	x
S7	On(D,Table) & On(B, Table) & On(A, Table) & On(C,D)	x	x	$\ch$

Finding conflicts:

as shown by tick indicator. For an operator in a plan/goal, find conflicts in other plans/goals. First let us identify where we need to check for conflicts, indicated by ?.

We could ignore all operators that are common for all plans also, for a moment,

Operator	Pre condition	S4	S5	S6	S7
Move(A,Table)	Clear(A)	?	_	_	_
Move(A,B)	Clear(A) & Clear(B)	_	?	?	?
Move(B,C)	Clear(B) & Clear(C)	?	_	_	?
Move(C,D)	Clear(C) & Clear(D)	?	?	?	_

Now marking the conflict by respective condition, and no conflict by x

Operator	Pre condition	S4	S5	S6	S7
Move(A,Table)	Clear(A)	x	_	_	_
Move(A,B)	Clear(A) & Clear(B)	_	x	x	x
Move(B,C)	Clear(B) & Clear(C)	On(A,B)	_	_	x
Move(C,D)	Clear(C) & Clear(D)	x	x	On(B,C)	_

Above table illustrates

• Move(C,D) of Goal:On(C,D) is clobbered by On(B,C) from S6 belonging to Goal:On(B,C)
• Move(B,C) of Goal:On(B,C) is clobbered by On(A,B) from S4 belonging to Goal:On(A,B)

Conclusion

So

• Prefer Goal:On(C,D) over Goal:On(B,C)
• Prefer Goal:On(B,C) over Goal:On(A,B)

This implies, the order

• Goal:On(C,D)
• Goal:On(B,C)
• Goal:On(A,B)

Quiz: POP V

Combining above Goals in order we get,

Hierarchical Decomposition

Decompose, abstract